package com.zx._12_算法.algorithm.math;

import org.junit.Test;

public class SqrtTest {

    /**
     * @Title: 1、古人算法（暴力法）
     * @Description: 原理：从0开始0.00001,000002...一个一个试，直到找到x的平方根
     * @date: 2019年11月15日下午12:35:58
     * @author: Administrator
     */
    @Test
    public void test1() {
        double x = 3;
        final double _JINGDU = 1e-6;
        double i = _JINGDU;
        while (true) {
            double a = i * i;
            if (a >= x) {
                break;
            } else {
                i += _JINGDU;
            }
        }
        //1.7320509999476947
        System.out.println(i);
    }

    /**
     * @Title: 2、牛顿迭代法
     * @Description: 计算机科班出身的童鞋可能首先会想到的是《数值分析》中的牛顿迭代法求平方根。
     *         原理是：随意选一个数比如说8，要求根号3，我们可以这么算：
     *         (8 + 3/8)/2 = 4.1875
     *         (4.1875 + 3/4.1875)/2 = 2.4519
     *         (2.4519 + 3/2.4519)/2 = 1.837
     *         (1.837 + 3/1.837)/2 = 1.735
     *         做了4步基本算出了近似值了，这种迭代的方式就是传说中的牛顿迭代法了
     * @date: 2019年11月15日下午12:35:58
     * @author: Administrator
     */
    @Test
    public void test2() {
        double x = 3;
        final double _JINGDU = 1e-6;

        double avg = x;
        double last_avg = Double.MAX_VALUE;
        while (true) {
            double abs = Math.abs(last_avg - avg);
            if (abs <= _JINGDU) {
                break;
            }
            last_avg = avg;
            avg = (avg + x / avg) / 2;
        }
        //1.7320508075688772
        System.out.println(avg);
    }

    /**
     * @Title: 3. 暴力-牛顿综合法
     * @Description: 原理：还是以根号3为例，先用暴力法讲根号3逼近到1.7，
     *         然后再利用上述的牛顿迭代法。虽然没有用牛顿迭代好，但是也为我们提供一种思路
     * @date: 2019年11月15日下午10:07:03
     * @author: zhangxue
     */
    @Test
    public void test3() {
        double x = 3;
        final double _JINGDU = 1e-6;

        double avg = x;
        double last_avg = Double.MAX_VALUE;

        double i = 0;
        while (true) {
            if (i * i >= x) {
                avg = i;
                break;
            } else {
                i += 0.1;
            }
        }

        while (true) {
            double abs = Math.abs(last_avg - avg);
            if (abs <= _JINGDU) {
                break;
            }
            last_avg = avg;
            avg = (avg + x / avg) / 2;
        }
        //1.7320508075689423
        System.out.println(avg);
    }

    /**
     * @Title: 4. 二分开方法
     * @Description: 直到前后两次平均值只差小于自定义精度为止
     *         (0+3)/2 = 1.5, 1.5^2 = 2.25, 2.25 < 3;
     *         (1.5+3)/2 = 2.25, 2.25^2 = 5.0625, 5.0625 > 3;
     *         (1.5+2.25)/2 = 1.875, 1.875^2 = 3.515625; 3.515625>3;
     * @date: 2019年11月15日下午10:24:26
     * @author: zhangxue
     */
    @Test
    public void test4() {
        double x = 3;
        final double _JINGDU = 1e-6;
        double _low = 0;
        double _high = x;
        double _mid = Double.MAX_VALUE;
        double last_mid = Double.MIN_VALUE;

        while (Math.abs(_mid - last_mid) > _JINGDU) {
            last_mid = _mid;
            _mid = (_low + _high) / 2;
            if (_mid * _mid > x) {
                _high = _mid;
            }
            if (_mid * _mid < x) {
                _low = _mid;
            }
        }
        System.out.println(_mid);
    }


}
